﻿/*
题目：从给定原材料中找到所有可以做出的菜

你有 n 道不同菜的信息。给你一个字符串数组 recipes 和一个二维字符串数组 ingredients 。第 i 道菜的名字为 recipes[i] ，如果你有它 所有 的原材料 ingredients[i] ，那么你可以 做出 这道菜。一道菜的原材料可能是 另一道 菜，也就是说 ingredients[i] 可能包含 recipes 中另一个字符串。

同时给你一个字符串数组 supplies ，它包含你初始时拥有的所有原材料，每一种原材料你都有无限多。

请你返回你可以做出的所有菜。你可以以 任意顺序 返回它们。

注意两道菜在它们的原材料中可能互相包含。

https://leetcode.cn/problems/find-all-possible-recipes-from-given-supplies/description/
*/

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include "TreeNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>

using namespace std;

class Solution {
public:
    // 制作 food[i] 需要的材料是 need[i], 我们拥有的总材料为 has
    vector<string> findAllRecipes(vector<string>& food, vector<vector<string>>& need,
        vector<string>& has) {
        // G[i][j] 表示制作 food[j] 需要用到 need[i]
        // 给食材编号
        unordered_map<string, int> need2id;
        for (int i = 0; i < need.size(); i++) {
            for (int j = 0; j < need[i].size(); j++) {
                if (need2id.count(need[i][j]) == false)
                    need2id.insert({ need[i][j], need2id.size() });
            }
        }
        for (int i = 0; i < has.size(); i++) {
            if (need2id.count(has[i]) == false)
                need2id.insert({ has[i], need2id.size() });
        }
        for (int i = 0; i < food.size(); i++) {
            if (need2id.count(food[i]) == false)
                need2id.insert({ food[i], need2id.size() });
        }

        // 构图
        vector<vector<bool>> G(need2id.size(), vector<bool>(food.size(), false));
        vector<int> in_degree(food.size(), 0);
        for (int i = 0; i < need.size(); i++) {
            for (int j = 0; j < need[i].size(); j++) {
                int u = need2id[need[i][j]];
                int v = i;
                G[u][v] = true;
                in_degree[v] ++;
            }
        }

        // 已经有的食材，更新入度
        queue<int> q;
        for (int i = 0; i < has.size(); i++) {
            int u = need2id[has[i]];
            for (int v = 0; v < food.size(); v++) {
                if (G[u][v] == true) {
                    in_degree[v] --;
                    if (in_degree[v] == 0) q.push(v);
                }
            }
        }

        // 开始拓扑
        vector<string> res;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            res.emplace_back(food[u]);
            u = need2id[food[u]];

            for (int v = 0; v < food.size(); v++) {
                if (G[u][v] == true) {
                    --in_degree[v];
                    if (in_degree[v] == 0) {
                        q.push(v);
                    }
                }
            }
        }

        return res;
    }
};
